<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
	<head>
		<title>Nonterminals</title>
<link href="../docs-assets/Breadcrumbs.css" rel="stylesheet" rev="stylesheet" type="text/css">
		<meta name="viewport" content="width=device-width initial-scale=1">
		<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
		<meta http-equiv="Content-Language" content="en-gb">

<link href="../docs-assets/Contents.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Progress.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Navigation.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Fonts.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Base.css" rel="stylesheet" rev="stylesheet" type="text/css">
<script>
function togglePopup(material_id) {
  var popup = document.getElementById(material_id);
  popup.classList.toggle("show");
}
</script>

<link href="../docs-assets/Popups.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Colours.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Preform-Colours.css" rel="stylesheet" rev="stylesheet" type="text/css">
		
	</head>
	<body class="commentary-font">
		<nav role="navigation">
		<h1><a href="../index.html"><img src="../docs-assets/Inform.png" height=72> </a></h1>
<ul><li><a href="../index.html">home</a></li>
</ul><h2>Compiler</h2><ul>
<li><a href="../structure.html">structure</a></li>
<li><a href="../inbuildn.html">inbuild</a></li>
<li><a href="../inform7n.html">inform7</a></li>
<li><a href="../intern.html">inter</a></li>
<li><a href="../services.html">services</a></li>
<li><a href="../secrets.html">secrets</a></li>
</ul><h2>Other Tools</h2><ul>
<li><a href="../inblorbn.html">inblorb</a></li>
<li><a href="../inform6.html">inform6</a></li>
<li><a href="../inpolicyn.html">inpolicy</a></li>
</ul><h2>Resources</h2><ul>
<li><a href="../extensions.html">extensions</a></li>
<li><a href="../kits.html">kits</a></li>
</ul><h2>Repository</h2><ul>
<li><a href="https://github.com/ganelson/inform"><img src="../docs-assets/github.png" height=0> github</a></li>
</ul><h2>Related Projects</h2><ul>
<li><a href="https://github.com/ganelson/inweb"><img src="../docs-assets/github.png" height=0> inweb</a></li>
<li><a href="https://github.com/ganelson/intest"><img src="../docs-assets/github.png" height=0> intest</a></li>
</ul>
		</nav>
		<main role="main">
		<!-- Weave of 'Nonterminals' generated by inweb -->
<div class="breadcrumbs">
    <ul class="crumbs"><li><a href="../index.html">Home</a></li><li><a href="../services.html">Services</a></li><li><a href="index.html">words</a></li><li><a href="index.html#4">Chapter 4: Parsing</a></li><li><b>Nonterminals</b></li></ul></div>
<p class="purpose">The angle-bracketed terms appearing in Preform grammar.</p>

<ul class="toc"><li><a href="4-nnt.html#SP1">&#167;1. How nonterminals are stored</a></li><li><a href="4-nnt.html#SP9">&#167;9. Word ranges in a nonterminal</a></li><li><a href="4-nnt.html#SP10">&#167;10. Other results</a></li><li><a href="4-nnt.html#SP11">&#167;11. Flagging and numbering</a></li></ul><hr class="tocbar">

<p class="commentary firstcommentary"><a id="SP1" class="paragraph-anchor"></a><b>&#167;1. How nonterminals are stored.</b>Each different nonterminal defined in the <span class="extract"><span class="extract-syntax">Syntax.preform</span></span> code read in,
such as &lt;any-integer&gt;, is going to correspond to a global variable in the
program reading it in, such as <span class="extract"><span class="extract-syntax">any_integer_NTM</span></span>. On the face of it, this is
impossible. How can what happens at run-time affect what variables are named
at compile time?
</p>

<p class="commentary">The answer is that the <a href="../inweb/index.html" class="internal">inweb</a> literate programming tool looks through the
complete source code, sees the Preform nonterminals described in it, and
inserts declarations of the corresponding variables into the "tangled" form
of the source code sent to a C compiler to make the actual program. (This is
a feature of <a href="../inweb/index.html" class="internal">inweb</a> available only for programs written in InC.)
</p>

<p class="commentary">In particular, the tangler of <span class="extract"><span class="extract-syntax">inweb</span></span> replaces the <span class="extract"><span class="extract-syntax">[[nonterminals]]</span></span> below with
invocations of the <span class="extract"><span class="extract-syntax">REGISTER_NONTERMINAL</span></span> and <span class="extract"><span class="extract-syntax">INTERNAL_NONTERMINAL</span></span> macros.
For example, it inserts the C line:
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="plain-syntax">    </span><span class="identifier-syntax">INTERNAL_NONTERMINAL</span><span class="plain-syntax">(</span><span class="identifier-syntax">U</span><span class="string-syntax">"&lt;any-integer&gt;"</span><span class="plain-syntax">, </span><span class="identifier-syntax">any_integer_NTM</span><span class="plain-syntax">, </span><span class="constant-syntax">1</span><span class="plain-syntax">, </span><span class="constant-syntax">1</span><span class="plain-syntax">);</span>
</pre>
<p class="commentary">since this is an "internal" nonterminal; and the macro will then expand
to code which sets up <span class="extract"><span class="extract-syntax">any_integer_NTM</span></span> &mdash; see below.
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">void</span><span class="plain-syntax"> </span><span class="function-syntax">Nonterminals::register</span><button class="popup" onclick="togglePopup('usagePopup1')"><span class="comment-syntax">?</span><span class="popuptext" id="usagePopup1">Usage of <span class="code-font"><span class="function-syntax">Nonterminals::register</span></span>:<br/>Words Module - <a href="1-wm.html#SP3">&#167;3</a></span></button><span class="plain-syntax">(</span><span class="reserved-syntax">void</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">    </span><span class="comment-syntax"> The following is not valid C, but causes Inweb to insert lines which are</span>
<span class="plain-syntax">    [[</span><span class="identifier-syntax">nonterminals</span><span class="plain-syntax">]];</span>
<span class="plain-syntax">    </span><span class="comment-syntax"> Back to regular C now</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">nonterminal</span><span class="plain-syntax"> *</span><span class="identifier-syntax">nt</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">LOOP_OVER</span><span class="plain-syntax">(</span><span class="identifier-syntax">nt</span><span class="plain-syntax">, </span><span class="reserved-syntax">nonterminal</span><span class="plain-syntax">)</span>
<span class="plain-syntax">        </span><span class="reserved-syntax">if</span><span class="plain-syntax"> ((</span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">marked_internal</span><span class="plain-syntax">) &amp;&amp; (</span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">internal_definition</span><span class="plain-syntax"> == </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">))</span>
<span class="plain-syntax">            </span><span class="identifier-syntax">internal_error</span><span class="plain-syntax">(</span><span class="string-syntax">"internal nonterminal has no definition function"</span><span class="plain-syntax">);</span>
<span class="plain-syntax">}</span>
</pre>
<p class="commentary firstcommentary"><a id="SP2" class="paragraph-anchor"></a><b>&#167;2. </b>So, then, <a href="../inweb/index.html" class="internal">inweb</a> tangles out code which uses the <span class="extract"><span class="extract-syntax">REGISTER_NONTERMINAL</span></span>
macro for any standard nonterminal, and also tangles a compositor function for
it; the name of which is the nonterminal's name with a <span class="extract"><span class="extract-syntax">C</span></span> suffix. For example,
suppose <a href="../inweb/index.html" class="internal">inweb</a> sees the following in the web it is tangling:
</p>

<pre class="Preform-displayed-code all-displayed-code code-font">
<span class="Preform-plain-syntax">    </span><span class="Preform-function-syntax">&lt;competitor&gt;</span><span class="Preform-plain-syntax"> </span><span class="Preform-reserved-syntax">::=</span>
<span class="Preform-plain-syntax">        </span><span class="Preform-constant-syntax">the</span><span class="Preform-plain-syntax"> </span><span class="Preform-constant-syntax">pacemaker</span><span class="Preform-plain-syntax"> </span><span class="Preform-reserved-syntax">|</span><span class="Preform-plain-syntax">              </span><span class="Preform-reserved-syntax">==&gt;</span><span class="Preform-plain-syntax"> { 1, - }</span>
<span class="Preform-plain-syntax">        </span><span class="Preform-function-syntax">&lt;ordinal-number&gt;</span><span class="Preform-plain-syntax"> </span><span class="Preform-constant-syntax">runner</span><span class="Preform-plain-syntax"> </span><span class="Preform-reserved-syntax">|</span><span class="Preform-plain-syntax">    </span><span class="Preform-reserved-syntax">==&gt;</span><span class="Preform-plain-syntax"> { pass 1 }</span>
<span class="Preform-plain-syntax">        </span><span class="Preform-constant-syntax">runner</span><span class="Preform-plain-syntax"> </span><span class="Preform-constant-syntax">no</span><span class="Preform-plain-syntax"> </span><span class="Preform-function-syntax">&lt;cardinal-number&gt;</span><span class="Preform-plain-syntax">  </span><span class="Preform-reserved-syntax">==&gt;</span><span class="Preform-plain-syntax"> { pass 1 }</span>
</pre>
<p class="commentary">It then tangles this macro usage into <a href="4-nnt.html#SP1" class="internal">Nonterminals::register</a> above:
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="plain-syntax">    </span><span class="identifier-syntax">REGISTER_NONTERMINAL</span><span class="plain-syntax">(</span><span class="identifier-syntax">U</span><span class="string-syntax">"&lt;competitor&gt;"</span><span class="plain-syntax">, </span><span class="identifier-syntax">competitor_NTM</span><span class="plain-syntax">);</span>
</pre>
<p class="commentary">And it also tangles matching declarations for:
</p>

<ul class="items"><li>(a) the global variable <span class="extract"><span class="extract-syntax">competitor_NTM</span></span>, of type <span class="extract"><span class="extract-syntax">nonterminal *</span></span>;
</li><li>(b) the "compositor function" <span class="extract"><span class="extract-syntax">competitor_NTMC</span></span>, which is a function to
deal with what happens when a successful match is made against the grammar &mdash;
this incorporates the material which <a href="../inweb/index.html" class="internal">inweb</a> finds to the right of the <span class="extract"><span class="extract-syntax">==&gt;</span></span>
markers in the Preform definition.
</li></ul>
<p class="commentary">But if we left things at that, we would find ourselves at run-time with
a null variable, a function not called from anywhere, and an instance
somewhere in memory of a nonterminal read in from Preform syntax and
called <span class="extract"><span class="extract-syntax">"&lt;competitor&gt;"</span></span>, but which has no apparent connection to either
the function or the variable. We clearly need to join these together.
</p>

<p class="commentary">And so the <span class="extract"><span class="extract-syntax">REGISTER_NONTERMINAL</span></span> macro expands to code which initialises the
variable to the nonterminal having its name, and then connects that to the
compositor function:
</p>

<pre class="definitions code-font"><span class="definition-keyword">define</span> <span class="identifier-syntax">REGISTER_NONTERMINAL</span><span class="plain-syntax">(</span><span class="identifier-syntax">quotedname</span><span class="plain-syntax">, </span><span class="identifier-syntax">identifier</span><span class="plain-syntax">)</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">identifier</span><span class="plain-syntax"> = </span><a href="4-nnt.html#SP8" class="function-link"><span class="function-syntax">Nonterminals::find</span></a><span class="plain-syntax">(</span><a href="2-vcb.html#SP15" class="function-link"><span class="function-syntax">Vocabulary::entry_for_text</span></a><span class="plain-syntax">(</span><span class="identifier-syntax">quotedname</span><span class="plain-syntax">));</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">identifier</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">compositor_fn</span><span class="plain-syntax"> = </span><span class="identifier-syntax">identifier</span><span class="plain-syntax">##</span><span class="identifier-syntax">C</span><span class="plain-syntax">;</span>
</pre>
<p class="commentary firstcommentary"><a id="SP3" class="paragraph-anchor"></a><b>&#167;3. </b>For example, this might expand to:
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="plain-syntax">    </span><span class="identifier-syntax">competitor_NTM</span><span class="plain-syntax"> = </span><span class="identifier-syntax">Nonterminals</span><span class="plain-syntax">::</span><span class="identifier-syntax">find</span><span class="plain-syntax">(</span><span class="identifier-syntax">Vocabulary</span><span class="plain-syntax">::</span><span class="identifier-syntax">entry_for_text</span><span class="plain-syntax">(</span><span class="identifier-syntax">U</span><span class="string-syntax">"&lt;competitor&gt;"</span><span class="plain-syntax">));</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">competitor_NTM</span><span class="plain-syntax">-&gt;</span><span class="identifier-syntax">compositor_fn</span><span class="plain-syntax"> = </span><span class="identifier-syntax">competitor_NTMC</span><span class="plain-syntax">;</span>
</pre>
<p class="commentary">Note that it is absolutely necessary that <span class="extract"><span class="extract-syntax">Nonterminals::find</span></span> does
return a nonterminal. But we can be sure that it does, since the function creates
a nonterminal object of that name even if one does not already exist.
</p>

<p class="commentary firstcommentary"><a id="SP4" class="paragraph-anchor"></a><b>&#167;4. </b>The position for internal nonterminals (i.e. those defined by a function
written by the programmer, not by Preform grammar lines) is similar:
</p>

<ul class="items"><li>(a) again there is a global variable, say <span class="extract"><span class="extract-syntax">any_integer_NTM</span></span>, of type <span class="extract"><span class="extract-syntax">nonterminal *</span></span>;
</li><li>(b) but now there is no compositor, and instead there is a function <span class="extract"><span class="extract-syntax">any_integer_NTMR</span></span>
which actually performs the parse directly.
</li></ul>
<p class="commentary">The <span class="extract"><span class="extract-syntax">INTERNAL_NONTERMINAL</span></span> macro similarly initialises and connects these
declarations. <span class="extract"><span class="extract-syntax">min</span></span> and <span class="extract"><span class="extract-syntax">max</span></span> are conveniences for speedy parsing, and supply
the minimum and maximum number of words that the nonterminal can match; these
are needed because the Preform optimiser can't see inside <span class="extract"><span class="extract-syntax">any_integer_NTMR</span></span> to
calculate those bounds for itself. <span class="extract"><span class="extract-syntax">max</span></span> can be infinity, in which case we
use the constant <span class="extract"><span class="extract-syntax">INFINITE_WORD_COUNT</span></span> for it.
</p>

<pre class="definitions code-font"><span class="definition-keyword">define</span> <span class="identifier-syntax">INTERNAL_NONTERMINAL</span><span class="plain-syntax">(</span><span class="identifier-syntax">quotedname</span><span class="plain-syntax">, </span><span class="identifier-syntax">identifier</span><span class="plain-syntax">, </span><span class="identifier-syntax">min</span><span class="plain-syntax">, </span><span class="identifier-syntax">max</span><span class="plain-syntax">)</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">identifier</span><span class="plain-syntax"> = </span><a href="4-nnt.html#SP8" class="function-link"><span class="function-syntax">Nonterminals::find</span></a><span class="plain-syntax">(</span><a href="2-vcb.html#SP15" class="function-link"><span class="function-syntax">Vocabulary::entry_for_text</span></a><span class="plain-syntax">(</span><span class="identifier-syntax">quotedname</span><span class="plain-syntax">));</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">identifier</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">opt</span><span class="plain-syntax">.</span><span class="element-syntax">nt_extremes</span><span class="plain-syntax"> = </span><a href="4-le.html#SP3" class="function-link"><span class="function-syntax">LengthExtremes::new</span></a><span class="plain-syntax">(</span><span class="identifier-syntax">min</span><span class="plain-syntax">, </span><span class="identifier-syntax">max</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">identifier</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">internal_definition</span><span class="plain-syntax"> = </span><span class="identifier-syntax">identifier</span><span class="plain-syntax">##</span><span class="identifier-syntax">R</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">identifier</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">marked_internal</span><span class="plain-syntax"> = </span><span class="identifier-syntax">TRUE</span><span class="plain-syntax">;</span>
</pre>
<p class="commentary firstcommentary"><a id="SP5" class="paragraph-anchor"></a><b>&#167;5. </b>So, then, the following rather lengthy class declaration shows what goes
into a nonterminal. Note that nonterminals are uniquely identifiable by their
names: there can be only one called, say, &lt;any-integer&gt;. This is why its
textual name is referred to as an "ID".
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">typedef</span><span class="plain-syntax"> </span><span class="reserved-syntax">struct</span><span class="plain-syntax"> </span><span class="reserved-syntax">nonterminal</span><span class="plain-syntax"> {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">struct</span><span class="plain-syntax"> </span><span class="reserved-syntax">vocabulary_entry</span><span class="plain-syntax"> *</span><span class="identifier-syntax">nonterminal_id</span><span class="plain-syntax">; </span><span class="comment-syntax"> e.g. </span><span class="extract"><span class="extract-syntax">"&lt;any-integer&gt;"</span></span>

<span class="plain-syntax">    </span><span class="comment-syntax"> For internal nonterminals</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">marked_internal</span><span class="plain-syntax">; </span><span class="comment-syntax"> has, or will be given, an internal definition...</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">int</span><span class="plain-syntax"> (*</span><span class="identifier-syntax">internal_definition</span><span class="plain-syntax">)(</span><span class="reserved-syntax">wording</span><span class="plain-syntax"> </span><span class="identifier-syntax">W</span><span class="plain-syntax">, </span><span class="reserved-syntax">int</span><span class="plain-syntax"> *</span><span class="identifier-syntax">result</span><span class="plain-syntax">, </span><span class="reserved-syntax">void</span><span class="plain-syntax"> **</span><span class="identifier-syntax">result_p</span><span class="plain-syntax">); </span><span class="comment-syntax"> ...this one</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">voracious</span><span class="plain-syntax">; </span><span class="comment-syntax"> if true, scans whole rest of word range</span>

<span class="plain-syntax">    </span><span class="comment-syntax"> For regular nonterminals</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">struct</span><span class="plain-syntax"> </span><span class="reserved-syntax">production_list</span><span class="plain-syntax"> *</span><span class="identifier-syntax">first_pl</span><span class="plain-syntax">; </span><span class="comment-syntax"> if not internal, this defines it</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">int</span><span class="plain-syntax"> (*</span><span class="identifier-syntax">compositor_fn</span><span class="plain-syntax">)(</span><span class="reserved-syntax">int</span><span class="plain-syntax"> *</span><span class="identifier-syntax">r</span><span class="plain-syntax">, </span><span class="reserved-syntax">void</span><span class="plain-syntax"> **</span><span class="identifier-syntax">rp</span><span class="plain-syntax">, </span><span class="reserved-syntax">int</span><span class="plain-syntax"> *</span><span class="identifier-syntax">i_s</span><span class="plain-syntax">, </span><span class="reserved-syntax">void</span><span class="plain-syntax"> **</span><span class="identifier-syntax">i_ps</span><span class="plain-syntax">, </span><span class="reserved-syntax">wording</span><span class="plain-syntax"> *</span><span class="identifier-syntax">i_W</span><span class="plain-syntax">, </span><span class="reserved-syntax">wording</span><span class="plain-syntax"> </span><span class="identifier-syntax">W</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">multiplicitous</span><span class="plain-syntax">; </span><span class="comment-syntax"> if true, matches are alternative syntax tree readings</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">number_words_by_production</span><span class="plain-syntax">; </span><span class="comment-syntax"> this parses names for numbers, like "huit" or "zwei"</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">unsigned</span><span class="plain-syntax"> </span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">flag_words_in_production</span><span class="plain-syntax">; </span><span class="comment-syntax"> all words in the production should get these flags</span>

<span class="plain-syntax">    </span><span class="comment-syntax"> Storage for most recent correct match</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">struct</span><span class="plain-syntax"> </span><span class="reserved-syntax">wording</span><span class="plain-syntax"> </span><span class="identifier-syntax">range_result</span><span class="plain-syntax">[</span><span class="constant-syntax">MAX_RANGES_PER_PRODUCTION</span><span class="plain-syntax">]; </span><span class="comment-syntax"> storage for word ranges matched</span>

<span class="plain-syntax">    </span><span class="reserved-syntax">struct</span><span class="plain-syntax"> </span><span class="reserved-syntax">nonterminal_optimisation_data</span><span class="plain-syntax"> </span><span class="identifier-syntax">opt</span><span class="plain-syntax">; </span><span class="comment-syntax"> see </span><a href="4-to.html" class="internal">The Optimiser</a>
<span class="plain-syntax">    </span><span class="reserved-syntax">struct</span><span class="plain-syntax"> </span><span class="reserved-syntax">nonterminal_instrumentation_data</span><span class="plain-syntax"> </span><span class="identifier-syntax">ins</span><span class="plain-syntax">; </span><span class="comment-syntax"> see </span><a href="4-ins.html" class="internal">Instrumentation</a>

<span class="plain-syntax">    </span><span class="identifier-syntax">CLASS_DEFINITION</span>
<span class="plain-syntax">} </span><span class="reserved-syntax">nonterminal</span><span class="plain-syntax">;</span>
</pre>
<ul class="endnotetexts"><li>The structure nonterminal is accessed in 4/lp, 4/to, 4/le, 4/ni, 4/prf, 4/ins, 4/pu and here.</li></ul>
<p class="commentary firstcommentary"><a id="SP6" class="paragraph-anchor"></a><b>&#167;6. </b>A few notes on this are in order:
</p>

<ul class="items"><li>(a) As noted above, every nonterminal is either "internal" or "regular". If
internal, it is defined by a function; if regular, it is defined by lines
of grammar (called "productions") and a compositor function.
</li><li>(b) A few internal nonterminals are "voracious". These are given the entire
word range for their productions to eat, and encouraged to eat as much as they
like, returning a word number to show how far they got. While this effect
could be duplicated with non-voracious nonterminals, that would be quite a bit
slower, since it would have to test every possible word range.
</li><li>(c) A few regular nonterminals are "multiplicitous". These composite their
results in a way special to the Inform compiler's syntax tree, by stacking
them up as alternative possible readings of the same text. Ordinarily, the
result of parsing text against a nonterminal is that the first grammar line
matching that text determines the meaning, but for a multiplicitous nonterminal,
every line matching the text determines one of perhaps many possible meanings.
</li><li>(d) For numbering and flagging on regular NTs, see <a href="4-nnt.html#SP11" class="internal">Nonterminals::make_numbering</a>
below.
</li><li>(e) The optimisation data helps the parser to reject non-matching text quickly.
For example, if the optimiser can determine that &lt;competitor&gt; only ever matches
texts of between 3 and 7 words in length, it can quickly reject any run of
words outside that range. (However: note that a maximum of 0 means that the
maximum and minimum word counts are disregarded.) The other fields are harder
to explain &mdash; see <a href="4-to.html" class="internal">The Optimiser</a>.
</li></ul>
<p class="commentary firstcommentary"><a id="SP7" class="paragraph-anchor"></a><b>&#167;7. </b>So, then, as noted above, nonterminals are identified by their name-words.
The following is not especially fast but doesn't need to be: it's used only
when Preform grammar is parsed, not when Inform text is parsed.
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">nonterminal</span><span class="plain-syntax"> *</span><span class="function-syntax">Nonterminals::detect</span><button class="popup" onclick="togglePopup('usagePopup2')"><span class="comment-syntax">?</span><span class="popuptext" id="usagePopup2">Usage of <span class="code-font"><span class="function-syntax">Nonterminals::detect</span></span>:<br/><a href="4-nnt.html#SP8">&#167;8</a><br/>Basic Nonterminals - <a href="4-bn.html#SP1">&#167;1</a></span></button><span class="plain-syntax">(</span><span class="reserved-syntax">vocabulary_entry</span><span class="plain-syntax"> *</span><span class="identifier-syntax">name_word</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">nonterminal</span><span class="plain-syntax"> *</span><span class="identifier-syntax">nt</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">LOOP_OVER</span><span class="plain-syntax">(</span><span class="identifier-syntax">nt</span><span class="plain-syntax">, </span><span class="reserved-syntax">nonterminal</span><span class="plain-syntax">)</span>
<span class="plain-syntax">        </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">name_word</span><span class="plain-syntax"> == </span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">nonterminal_id</span><span class="plain-syntax">)</span>
<span class="plain-syntax">            </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="identifier-syntax">nt</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">;</span>
<span class="plain-syntax">}</span>
</pre>
<p class="commentary firstcommentary"><a id="SP8" class="paragraph-anchor"></a><b>&#167;8. </b>And the following always returns one, creating it if necessary:
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">nonterminal</span><span class="plain-syntax"> *</span><span class="function-syntax">Nonterminals::find</span><button class="popup" onclick="togglePopup('usagePopup3')"><span class="comment-syntax">?</span><span class="popuptext" id="usagePopup3">Usage of <span class="code-font"><span class="function-syntax">Nonterminals::find</span></span>:<br/><a href="4-nnt.html#SP2">&#167;2</a>, <a href="4-nnt.html#SP4">&#167;4</a><br/>Loading Preform - <a href="4-lp.html#SP7_2">&#167;7.2</a>, <a href="4-lp.html#SP7_3">&#167;7.3</a>, <a href="4-lp.html#SP16_2">&#167;16.2</a></span></button><span class="plain-syntax">(</span><span class="reserved-syntax">vocabulary_entry</span><span class="plain-syntax"> *</span><span class="identifier-syntax">name_word</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">nonterminal</span><span class="plain-syntax"> *</span><span class="identifier-syntax">nt</span><span class="plain-syntax"> = </span><a href="4-nnt.html#SP7" class="function-link"><span class="function-syntax">Nonterminals::detect</span></a><span class="plain-syntax">(</span><span class="identifier-syntax">name_word</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">nt</span><span class="plain-syntax"> == </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">nt</span><span class="plain-syntax"> = </span><span class="identifier-syntax">CREATE</span><span class="plain-syntax">(</span><span class="reserved-syntax">nonterminal</span><span class="plain-syntax">);</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">nonterminal_id</span><span class="plain-syntax"> = </span><span class="identifier-syntax">name_word</span><span class="plain-syntax">;</span>

<span class="plain-syntax">        </span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">marked_internal</span><span class="plain-syntax"> = </span><span class="identifier-syntax">FALSE</span><span class="plain-syntax">; </span><span class="comment-syntax"> by default, nonterminals are regular</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">internal_definition</span><span class="plain-syntax"> = </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">;</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">voracious</span><span class="plain-syntax"> = </span><span class="identifier-syntax">FALSE</span><span class="plain-syntax">;</span>

<span class="plain-syntax">        </span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">first_pl</span><span class="plain-syntax"> = </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">;</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">compositor_fn</span><span class="plain-syntax"> = </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">;</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">multiplicitous</span><span class="plain-syntax"> = </span><span class="identifier-syntax">FALSE</span><span class="plain-syntax">;</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">number_words_by_production</span><span class="plain-syntax"> = </span><span class="identifier-syntax">FALSE</span><span class="plain-syntax">; </span><span class="comment-syntax"> i.e., don't</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">flag_words_in_production</span><span class="plain-syntax"> = </span><span class="constant-syntax">0</span><span class="plain-syntax">; </span><span class="comment-syntax"> i.e., apply no flags</span>

<span class="plain-syntax">        </span><span class="reserved-syntax">for</span><span class="plain-syntax"> (</span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">i</span><span class="plain-syntax">=0; </span><span class="identifier-syntax">i</span><span class="plain-syntax">&lt;</span><span class="constant-syntax">MAX_RANGES_PER_PRODUCTION</span><span class="plain-syntax">; </span><span class="identifier-syntax">i</span><span class="plain-syntax">++)</span>
<span class="plain-syntax">            </span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">range_result</span><span class="plain-syntax">[</span><span class="identifier-syntax">i</span><span class="plain-syntax">] = </span><span class="constant-syntax">EMPTY_WORDING</span><span class="plain-syntax">;</span>

<span class="plain-syntax">        </span><a href="4-to.html#SP2" class="function-link"><span class="function-syntax">Optimiser::initialise_nonterminal_data</span></a><span class="plain-syntax">(&amp;(</span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">opt</span><span class="plain-syntax">));</span>
<span class="plain-syntax">        </span><a href="4-ins.html#SP2" class="function-link"><span class="function-syntax">Instrumentation::initialise_nonterminal_data</span></a><span class="plain-syntax">(&amp;(</span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">ins</span><span class="plain-syntax">));</span>
<span class="plain-syntax">    }</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="identifier-syntax">nt</span><span class="plain-syntax">;</span>
<span class="plain-syntax">}</span>
</pre>
<p class="commentary firstcommentary"><a id="SP9" class="paragraph-anchor"></a><b>&#167;9. Word ranges in a nonterminal.</b>We now need to define the macros <span class="extract"><span class="extract-syntax">GET_RW</span></span> and <span class="extract"><span class="extract-syntax">PUT_RW</span></span>, which get and set
the results of a successful match against a nonterminal (see <a href="4-ap.html" class="internal">About Preform</a>
for more on this).
</p>

<p class="commentary">We do so by giving each nonterminal a small array of <span class="extract"><span class="extract-syntax">wording</span></span>s, which are
lightweight structures incurring little time or space overhead. The fact that
they are attached to the NT itself, rather than, say, being placed on a
parsing stack of some kind, makes them faster to access, but is possible only
because the parser never backtracks. Similarly, results word ranges are
overwritten if a nonterminal calls itself directly or indirectly: that is, the
inner one's results are wiped out by the outer one. But this is no problem,
since we never extract word-ranges from grammar which is recursive.
</p>

<p class="commentary">Word range 0 is reserved in case we ever need it for the entire text matched
by the nonterminal, though at present we don't need that.
</p>

<pre class="definitions code-font"><span class="definition-keyword">define</span> <span class="constant-syntax">MAX_RANGES_PER_PRODUCTION</span><span class="plain-syntax"> </span><span class="constant-syntax">5</span><span class="plain-syntax"> </span><span class="comment-syntax"> in fact, one less than this, since range 0 is reserved</span>
<span class="definition-keyword">define</span> <span class="identifier-syntax">GET_RW</span><span class="plain-syntax">(</span><span class="identifier-syntax">nt</span><span class="plain-syntax">, </span><span class="identifier-syntax">N</span><span class="plain-syntax">) (</span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">range_result</span><span class="plain-syntax">[</span><span class="identifier-syntax">N</span><span class="plain-syntax">])</span>
<span class="definition-keyword">define</span> <span class="identifier-syntax">PUT_RW</span><span class="plain-syntax">(</span><span class="identifier-syntax">nt</span><span class="plain-syntax">, </span><span class="identifier-syntax">N</span><span class="plain-syntax">, </span><span class="identifier-syntax">W</span><span class="plain-syntax">) { </span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">range_result</span><span class="plain-syntax">[</span><span class="identifier-syntax">N</span><span class="plain-syntax">] = </span><span class="identifier-syntax">W</span><span class="plain-syntax">; }</span>
<span class="definition-keyword">define</span> <span class="identifier-syntax">INHERIT_RANGES</span><span class="plain-syntax">(</span><span class="identifier-syntax">from</span><span class="plain-syntax">, </span><span class="identifier-syntax">to</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">for</span><span class="plain-syntax"> (</span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">i</span><span class="plain-syntax">=1; </span><span class="identifier-syntax">i</span><span class="plain-syntax">&lt;</span><span class="constant-syntax">MAX_RANGES_PER_PRODUCTION</span><span class="plain-syntax">; </span><span class="identifier-syntax">i</span><span class="plain-syntax">++) </span><span class="comment-syntax"> not copying range 0</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">to</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">range_result</span><span class="plain-syntax">[</span><span class="identifier-syntax">i</span><span class="plain-syntax">] = </span><span class="identifier-syntax">from</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">range_result</span><span class="plain-syntax">[</span><span class="identifier-syntax">i</span><span class="plain-syntax">];</span>
<span class="plain-syntax">}</span>
<span class="definition-keyword">define</span> <span class="identifier-syntax">CLEAR_RW</span><span class="plain-syntax">(</span><span class="identifier-syntax">from</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">for</span><span class="plain-syntax"> (</span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">i</span><span class="plain-syntax">=0; </span><span class="identifier-syntax">i</span><span class="plain-syntax">&lt;</span><span class="constant-syntax">MAX_RANGES_PER_PRODUCTION</span><span class="plain-syntax">; </span><span class="identifier-syntax">i</span><span class="plain-syntax">++) </span><span class="comment-syntax"> including range 0</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">from</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">range_result</span><span class="plain-syntax">[</span><span class="identifier-syntax">i</span><span class="plain-syntax">] = </span><span class="constant-syntax">EMPTY_WORDING</span><span class="plain-syntax">;</span>
<span class="plain-syntax">}</span>
</pre>
<p class="commentary firstcommentary"><a id="SP10" class="paragraph-anchor"></a><b>&#167;10. Other results.</b>The parser records the result of the most recently matched nonterminal in the
following global variables &mdash; which, unlike word ranges, are not attached to
any single NT.
</p>

<p class="commentary"><a href="../inweb/index.html" class="internal">inweb</a> translates the notation <span class="extract"><span class="extract-syntax">&lt;&lt;r&gt;&gt;</span></span> and <span class="extract"><span class="extract-syntax">&lt;&lt;rp&gt;&gt;</span></span> to these variable names:
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">most_recent_result</span><span class="plain-syntax"> = </span><span class="constant-syntax">0</span><span class="plain-syntax">; </span><span class="comment-syntax"> the variable which </span><span class="extract"><span class="extract-syntax">inweb</span></span><span class="comment-syntax"> writes </span><span class="extract"><span class="extract-syntax">&lt;&lt;r&gt;&gt;</span></span>
<span class="reserved-syntax">void</span><span class="plain-syntax"> *</span><span class="identifier-syntax">most_recent_result_p</span><span class="plain-syntax"> = </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">; </span><span class="comment-syntax"> the variable which </span><span class="extract"><span class="extract-syntax">inweb</span></span><span class="comment-syntax"> writes </span><span class="extract"><span class="extract-syntax">&lt;&lt;rp&gt;&gt;</span></span>
</pre>
<p class="commentary firstcommentary"><a id="SP11" class="paragraph-anchor"></a><b>&#167;11. Flagging and numbering.</b>The following mechanism arranges for words used in the grammar for a NT to
be given properties just because of that &mdash; either flags or numerical values.
For example, if we wanted the numbers from Stoppard's play "Dogg's Hamlet",
we might have:
</p>

<pre class="Preform-displayed-code all-displayed-code code-font">
<span class="Preform-plain-syntax">    </span><span class="Preform-function-syntax">&lt;dogg-numbers&gt;</span><span class="Preform-plain-syntax"> </span><span class="Preform-reserved-syntax">::=</span>
<span class="Preform-plain-syntax">        </span><span class="Preform-constant-syntax">sun</span><span class="Preform-plain-syntax"> </span><span class="Preform-reserved-syntax">|</span><span class="Preform-plain-syntax"> </span><span class="Preform-constant-syntax">dock</span><span class="Preform-plain-syntax"> </span><span class="Preform-reserved-syntax">|</span><span class="Preform-plain-syntax"> </span><span class="Preform-constant-syntax">trog</span><span class="Preform-plain-syntax"> </span><span class="Preform-reserved-syntax">|</span><span class="Preform-plain-syntax"> </span><span class="Preform-constant-syntax">slack</span><span class="Preform-plain-syntax"> </span><span class="Preform-reserved-syntax">|</span><span class="Preform-plain-syntax"> </span><span class="Preform-constant-syntax">pan</span>
</pre>
<p class="commentary">And if &lt;dogg-numbers&gt; were made a "numbering" NT, the effect would be that
these five words would pick up the numerical values 1, 2, 3, 4, 5, because
they occur in production number 1, 2, 3, 4, 5 for the NT.
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">void</span><span class="plain-syntax"> </span><span class="function-syntax">Nonterminals::make_numbering</span><span class="plain-syntax">(</span><span class="reserved-syntax">nonterminal</span><span class="plain-syntax"> *</span><span class="identifier-syntax">nt</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">number_words_by_production</span><span class="plain-syntax"> = </span><span class="identifier-syntax">TRUE</span><span class="plain-syntax">;</span>
<span class="plain-syntax">}</span>
</pre>
<p class="commentary firstcommentary"><a id="SP12" class="paragraph-anchor"></a><b>&#167;12. </b>Similarly, we could flag this NT with <span class="extract"><span class="extract-syntax">NUMBER_MC</span></span>, and then the five words
sun, dock, trog, slack, pan would all pick up the <span class="extract"><span class="extract-syntax">NUMBER_MC</span></span> flag
automatically.
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">void</span><span class="plain-syntax"> </span><span class="function-syntax">Nonterminals::flag_words_with</span><span class="plain-syntax">(</span><span class="reserved-syntax">nonterminal</span><span class="plain-syntax"> *</span><span class="identifier-syntax">nt</span><span class="plain-syntax">, </span><span class="reserved-syntax">unsigned</span><span class="plain-syntax"> </span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">flags</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">flag_words_in_production</span><span class="plain-syntax"> = </span><span class="identifier-syntax">flags</span><span class="plain-syntax">;</span>
<span class="plain-syntax">}</span>
</pre>
<p class="commentary firstcommentary"><a id="SP13" class="paragraph-anchor"></a><b>&#167;13. </b>This is all done by the following function, which is called when a word <span class="extract"><span class="extract-syntax">ve</span></span>
is read as part of a production with match number <span class="extract"><span class="extract-syntax">pc</span></span> for the nonterminal <span class="extract"><span class="extract-syntax">nt</span></span>:
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">void</span><span class="plain-syntax"> </span><span class="function-syntax">Nonterminals::note_word</span><button class="popup" onclick="togglePopup('usagePopup4')"><span class="comment-syntax">?</span><span class="popuptext" id="usagePopup4">Usage of <span class="code-font"><span class="function-syntax">Nonterminals::note_word</span></span>:<br/>Loading Preform - <a href="4-lp.html#SP16_3">&#167;16.3</a></span></button><span class="plain-syntax">(</span><span class="reserved-syntax">vocabulary_entry</span><span class="plain-syntax"> *</span><span class="identifier-syntax">ve</span><span class="plain-syntax">, </span><span class="reserved-syntax">nonterminal</span><span class="plain-syntax"> *</span><span class="identifier-syntax">nt</span><span class="plain-syntax">, </span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">pc</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">ve</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">flags</span><span class="plain-syntax"> |= (</span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">flag_words_in_production</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">nt</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">number_words_by_production</span><span class="plain-syntax">) </span><span class="identifier-syntax">ve</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">literal_number_value</span><span class="plain-syntax"> = </span><span class="identifier-syntax">pc</span><span class="plain-syntax">;</span>
<span class="plain-syntax">}</span>
</pre>
<nav role="progress"><div class="progresscontainer">
    <ul class="progressbar"><li class="progressprev"><a href="4-ap.html">&#10094;</a></li><li class="progresschapter"><a href="P-wtmd.html">P</a></li><li class="progresschapter"><a href="1-wm.html">1</a></li><li class="progresschapter"><a href="2-vcb.html">2</a></li><li class="progresschapter"><a href="3-lxr.html">3</a></li><li class="progresscurrentchapter">4</li><li class="progresssection"><a href="4-ap.html">ap</a></li><li class="progresscurrent">nnt</li><li class="progresssection"><a href="4-lp.html">lp</a></li><li class="progresssection"><a href="4-to.html">to</a></li><li class="progresssection"><a href="4-le.html">le</a></li><li class="progresssection"><a href="4-ni.html">ni</a></li><li class="progresssection"><a href="4-prf.html">prf</a></li><li class="progresssection"><a href="4-bn.html">bn</a></li><li class="progresssection"><a href="4-ins.html">ins</a></li><li class="progresssection"><a href="4-pu.html">pu</a></li><li class="progressnext"><a href="4-lp.html">&#10095;</a></li></ul></div>
</nav><!-- End of weave -->

		</main>
	</body>
</html>

